#include<iostream>
using namespace std;
  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 
class Solution {
public:

    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* slow = head, * fast = slow,*pre=nullptr;
        while (fast && fast->next) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        if (pre)
            pre->next = nullptr;
        ListNode* a1 = sortList(head), * a2 = sortList(slow),*help,*start=nullptr;
        if (a1 && (a2 == nullptr || a1->val <= a2->val))
            help = a1;
        else
            help = a2;
        start = help;
        while (a1 && a2) {
            ListNode* now;
            if (a1->val <= a2->val) {
                now = a1;
                a1 = a1->next;   
            }
            else {
                now = a2;
                a2 = a2->next;
            }
            start->next = now;
            start = start->next;
        }
        if (a1)
            start->next = a1;
        else
            start->next = a2;
        return help;
    }
};